1. Field of the Invention
The present invention relates generally to a digital processing system with a network of devices or nodes that communicate via a serial data communication ring via data packets, and more particularly, to a novel method and apparatus for removing unwanted (referred to as "rogue") data packets from the serial ring.
2. Description of the Prior Art
Sharing information between computer systems is well known in the art. The speed at which computing technology is evolving has placed increasing demands on the need to share information between computer systems. One method of sharing data between computers that has achieved widespread recognition is the use of traditional computer networking standards, such as Ethernet, or for increased speed, Fiber Distributed Data Interface ("FDDI") networks. Moreover, the ever increasing need for faster and deterministic performance has prompted the development of newer and more robust networking schemes.
Several prior art networks employ a ring topology (FIG. 1) in which data is passed from node to node around the ring until either: (a) the data has reached the intended recipient node, or (b) until it has reached all nodes on the ring. In either case, there must be some method of removing the data from the ring.
In the case of an intended destination, the address ("Node ID") of the intended recipient is included in the packet with the data. The recipient node, recognizing that the data is intended for that node, does not pass the packet to the next node on the ring, hence removing the packet from the ring.
In the case of a system in which the data is intended to reach all nodes on the ring, two prior art methods of removing the data from the ring are known to the inventors. A discussion of these two methods and their relative merits follows:
Embedded Address "Node ID" Method. The first method is to embed the address of the originating node ("Node ID") into a field within the data packet. Once the data packet has traveled completely around the ring and returns to the originating node, the originating node recognizes the packet as its own by the "Node ID" in the packet. The originating node removes the packet from the ring by simply not retransmitting the packet to the next node on the ring. In addition to facilitating the removal of data packets that have traveled completely around the network, there are several reasons why having the address of the originating node embedded in the data packet can be advantageous. For instance, the "Node ID" of the originating node might be used by the recipients to define where to store the data, or it can be used in some other way in which the application software would associate the data with the identification of the originating node. In addition, the presence of the originating "Node ID" can be very valuable in performing network diagnostics. However, one problem with the Node ID method of removing data packets is the possibility of a hardware fault causing the originating node to be unavailable to remove the data packet. For instance, if the originating node introduced a data packet onto the ring, and then immediately, through some hardware fault or data corruption, became unable to remove that data packet, the data packet would travel continuously around the data ring. This would result in the possibility of corrupting valid data and would consume network bandwidth. This packet is commonly called a "rogue data packet" or "rogue packet." Although rogue data packets rarely occur in normal operation, a removal method that accounts for rogue data packets is desirable.
Counter Method. A second data packet removal method that accounts for rogue packets is the "counter" method. In the counter method, each node is programmed with knowledge of the total number of nodes on the network, either through software, a dip-switch setting, or some other means. Then, the originating node sets a "counter field" within the data packet equal to the total number of nodes on the ring. As the data packet is received at each node, that node decrements the counter field by one and tests to see if the counter has reached zero. If the counter has reached zero, the data packet is removed. If the counter has not reached zero, then the data packet is processed normally and forwarded to the next node, until the counter does reach zero. Other variations of the counter method are possible, but the essence is that the packet is removed after having traveled through some predetermined number of nodes. The counter method is able to remove rogue data packets because it does not rely on the address of the originating node. Under normal operation, the originating node will remove its own data packets because the counter reaches zero when the data packet has traveled once completely around the serial ring. However, if the originating node fails, the counter will reach zero at the next node on the data ring, and that node will remove the data packet. Although this method accounts for rogue packets, one problem is that this method loses all the advantages of having the address of the originating node embedded within the data packet.
The ideal solution is to use a combination of the two methods described. However, the problem with including both a counter field and an originating "Node ID" in the data packet itself is the consumption of data space in the packet. The number of bits needed for the counter field and for the "Node ID" is a function of the maximum number of nodes the network can accommodate. For example, to allow a maximum of 32 nodes, 5 bits would be required in the counter field and another 5 bits for the "Node ID." To accommodate 256 nodes, a total of 16 bits would be required, 8 for the counter field, and 8 for the "Node ID."
Further, network technologies typically do not allow adding only the necessary number of additional bits to the data packet to accommodate having both a Node ID and a counter mechanism. Rather, the size of the data packet is driven by the buswidth of the circuitry used to encode and decode the data for transmission on a data path. For example, if the buswidth of the encoder/decoder was 32 bits, and the total number of bits necessary to carry all the information needed in the packet was 97, then four 32 bit words would be required to carry the information, since 3 words can carry only 96 bits. In this example, system performance would be significantly enhanced if one bit could be removed from the packet. The presence of both the counter field and the "Node ID" adds to the number of required bits and may reduce system performance more than the addition of a few bits would imply.
A second disadvantage of the counter method is that it requires a high speed circuit to subtract one from the counter field and a circuit to detect that the counter field is zero. It also requires additional storage devices and buffers to process the added bits. This additional hardware must be present on each node, and can increase the system cost.
Therefore, a need exists for an apparatus and a method for removing unwanted data packets that include both the advantages of originating node addressing as well as fault tolerance of the counter method, without adding a large number of bits to the packet, without adding significant additional cost, and without substantially adversely affecting overall system performance. The present invention teaches such an apparatus and method.
3. Prior Art Related to the Preferred Embodiment
The preferred embodiment of this invention is a data processing system that includes at least two nodes linked together in a ring topology. Each node could be an independent computer, or other device capable of reading from or writing to memory. The nodes are linked by a unidirectional data transmission path in which data is passed from node to node around the ring until all nodes have had access to the data. Within each node is a memory device, called global memory, which is coupled to the unidirectional data transmission path. When one node updates a data item stored in global memory (i.e., writes to global memory) that data and its corresponding address within the global memory is transported by the unidirectional data transmission path to all other nodes on the ring. The data is then place in the global memory of each node at the address associated with the data. By this method each node's global memory is a replica of the global memory in all of the other nodes.
Vince, European patent 0 092 895, and U.S. Pat. No. 4,562,539, titled "Data Processing System," teaches a system similar to that just described. The Vince patent describes a token passing system in which each node on the ring is given a turn to transmit its data and is also responsible for removing that data from the ring. The token passing system allows only one node, at a time, to originate data. The originating node removes all data from the ring before passing the token to the next node.
Vince does not address the possibility that the originating node might fail to remove its data from the ring. The present invention can be applied to and used with a system as described and taught by Vince.
The preferred embodiment described herein is an enhancement of a prior art system developed by the inventors that implements the unidirectional serial data transmission path with a 1.2 Giga Baud fiber optic link and a 96 bit packet that contains 32 bits of data, 23 bits of address, 8 bits of "Node ID," and other parity and control signals.